package code.mySpecializedTraining;


import utils.TreeNode;

import java.util.*;

/**
 * @author 26029
 * @date 2025/4/13
 * @description
 */
public class Greedy {
    // 455. 分发饼干
    public int findContentChildren(int[] g, int[] s) {
        // 1 <= g.length <= 3 * 10^4
        // 0 <= s.length <= 3 * 10^4
        int lenG = g.length, lenS = s.length;
        Arrays.sort(g);
        Arrays.sort(s);
        int posG = 0, posS = 0;
        int count = 0;
        while (posG < lenG && posS < lenS) {
            if (s[posS] >= g[posG]) {
                count++;
                posG++;
            }
            posS++;
        }
        return count;
    }

    // 376. 摆动序列 Greedy
    public int wiggleMaxLength(int[] nums) {
        // 1 <= nums.length <= 1000
        int len = nums.length;
        int ans = 1;
        int nowDirection = 0;
        for (int i = 1; i < len; i++) {
            if (nums[i] > nums[i - 1] && nowDirection != 1) {
                nowDirection = 1;
                ans++;
            } else if (nums[i] < nums[i - 1] && nowDirection != -1) {
                nowDirection = -1;
                ans++;
            }
        }
        return ans;
    }

    // 376. 摆动序列 DP
    public int wiggleMaxLength_dp(int[] nums) {
        int len = nums.length;
        int[] up = new int[len]; // upping[i]表示前i个元素到某个元素为止，正在上升的最长摆动序列长度
        int[] down = new int[len]; // downing[i]表示前i个元素到某个元素为止，正在下降的最长摆动序列长度
        up[0] = 1;
        down[0] = 1;
        for (int i = 1; i < len; i++) {
            up[i] = nums[i] > nums[i - 1] ? Math.max(up[i - 1], down[i - 1] + 1) : up[i - 1];
            down[i] = nums[i] < nums[i - 1] ? Math.max(down[i - 1], up[i - 1] + 1) : down[i - 1];
        }
        return Math.max(up[len - 1], down[len - 1]);
    }

    // 53. 最大子数组和
    public int maxSubArray(int[] nums) {
        // 1 <= nums.length <= 105
        int len = nums.length;
        int nowSum = nums[0];
        int max = nowSum;
        for (int i = 1; i < len; i++) {
            nowSum = Math.max(nowSum + nums[i], nums[i]);
            if (nowSum > max)
                max = nowSum;
        }
        return max;
    }

    // 55. 跳跃游戏
    public boolean canJump(int[] nums) {
        // 1 <= nums.length <= 104
        int len = nums.length;
        int farest = 0;
        for (int i = 0; i < len; i++) {
            if (i > farest)
                return false;
            farest = Math.max(farest, i + nums[i]);
        }
        return true;
    }

    // 45. 跳跃游戏 II
    public int jump(int[] nums) {
        // 找到当前第x步能跳的最远位置，到了这个最远位置还没结束的话，就把跳跃数增加
        // 1 <= nums.length <= 104
        int len = nums.length;
        int farest = 0; // 表示当前位置能跳到的最远距离
        int next_jump = 0; // 表示这一步能跳到的最远距离
        int jump_step = 0;
        for (int i = 0; i < len; i++) {
            farest = Math.max(farest, i + nums[i]);
            if (i == next_jump && i != len - 1) {
                jump_step++;
                next_jump = farest;
            }
        }
        return jump_step;
    }

    // 1005. K 次取反后最大化的数组和
    public int largestSumAfterKNegations(int[] nums, int k) {
        // 1 <= nums.length <= 104  1 <= k <= 104
        int len = nums.length;
        // 先排序，把负数都排到左面
        Arrays.sort(nums);
        // 遍历数组，消耗k
        for (int i = 0; i < len; i++) {
            if (nums[i] >= 0 || k == 0)
                break;
            nums[i] = -nums[i];
            k--;
        }
        if (k % 2 == 0)
            return Arrays.stream(nums).sum();
        Arrays.sort(nums);
        nums[0] = -nums[0];
        return Arrays.stream(nums).sum();
    }

    // 134. 加油站
    public int canCompleteCircuit(int[] gas, int[] cost) {
        // 1 <= n <= 105
        int n = gas.length;
        int i = 0, next;
        while (i < n) {
            next = i + 1;
            int nowPos = i;
            int nowGas = 0;
            int nowLen = 0;
            while (nowLen < n) {
                nowGas += gas[nowPos % n];
                if (nowGas < cost[nowPos % n]) {
                    // 如果在nowPos这里不符合了，说明下一个直接看nowPos+1位置就行，i+1到nowPos就不用看了
                    next = nowPos + 1;
                    break;
                }
                nowGas -= cost[nowPos % n];
                nowLen++;
                nowPos = nowPos + 1;
            }
            // 如果从i成功遍历了n次，说明符合条件
            if (nowLen == n)
                return i;

            i = next;
        }
        return -1;
    }

    // 135. 分发糖果
    public int candy(int[] ratings) {
        int len = ratings.length;
        int[] candy = new int[len];
        Arrays.fill(candy, 1);
        // 如果他比左面大，则比左面多一个
        for (int i = 1; i < len; i++) {
            if (ratings[i] > ratings[i - 1])
                candy[i] = candy[i - 1] + 1;
        }
        // 如果他比右面大，且没有右面多，则比右面多一个
        for (int i = len - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1] && candy[i] <= candy[i + 1])
                candy[i] = candy[i + 1] + 1;
        }
        return Arrays.stream(candy).sum();
    }

    // 406. 根据身高重建队列
    public int[][] reconstructQueue(int[][] people) {
        // 1 <= people.length <= 2000
        int len = people.length;
        int[][] ans = new int[len][2];
        // 排序
        Arrays.sort(people, ((o1, o2) -> {
            // 身高不相等，用身高 小→大
            if (o1[0] != o2[0])
                return Integer.compare(o1[0], o2[0]);
                // 身高相等，用他前面有多少个大于等于他的排，k大→k小
            else
                return Integer.compare(o2[1], o1[1]);
        }));
        // 获取位置
        List<Integer> posList = new ArrayList<>();
        for (int i = 0; i < len; i++) {
            posList.add(i);
        }
        // 根据顺序给位置
        for (int i = 0; i < len; i++) {
            int[] person = people[i];
            ans[posList.get(person[1])] = person;
            posList.remove(person[1]);
        }
        return ans;
    }

    // 452. 用最少数量的箭引爆气球
    public int findMinArrowShots(int[][] points) {
        // 1 <= points.length <= 105
        int len = points.length;
        Arrays.sort(points, (o1, o2) -> Integer.compare(o1[0], o2[0]));
        int arrows = 1;
        int nowLeft = 0, nowRight = Integer.MAX_VALUE;
        for (int i = 0; i < len; i++) {
            if (nowRight < points[i][0]) {
                arrows++;
                nowLeft = points[i][0];
                nowRight = points[i][1];
            } else {
                nowLeft = Math.max(nowLeft, points[i][0]);
                nowRight = Math.min(nowRight, points[i][1]);
            }
        }
        return arrows;
    }

    // 435. 无重叠区间
    public int eraseOverlapIntervals(int[][] intervals) {
        // 1 <= intervals.length <= 105
        int len = intervals.length;
        Arrays.sort(intervals, (o1, o2) -> Integer.compare(o1[0], o2[0]));
        int eraseNum = 0;
        int nowRight = intervals[0][1];
        for (int i = 1; i < len; i++) {
            if (nowRight > intervals[i][0]) {
                eraseNum++;
                nowRight = Math.min(nowRight, intervals[i][1]);
            } else {
                nowRight = intervals[i][1];
            }
        }
        return eraseNum;
    }

    // 763. 划分字母区间
    public List<Integer> partitionLabels(String s) {
        // 1 <= s.length <= 500
        int len_s = s.length();
        Map<Character, Integer> mapLeft = new HashMap<>(), mapRight = new HashMap<>();
        for (int i = 0; i < len_s; i++) {
            char c = s.charAt(i);
            mapRight.put(c, i);
        }
        for (int i = len_s - 1; i >= 0; i--) {
            char c = s.charAt(i);
            mapLeft.put(c, i);
        }
        int len_intervals = mapLeft.size();
        int[][] intervals = new int[len_intervals][2];
        int pos = 0;
        for (Character c : mapLeft.keySet()) {
            int left = mapLeft.get(c);
            int right = mapRight.get(c);
            intervals[pos] = new int[]{left, right};
            pos++;
        }
        Arrays.sort(intervals, ((o1, o2) -> Integer.compare(o1[0], o2[0])));
        // 找到答案
        List<Integer> ans = new ArrayList<>();
        int nowLeft = intervals[0][0], nowRight = intervals[0][1];
        for (int i = 1; i < len_intervals; i++) {
            if (nowRight > intervals[i][0]) {
                nowRight = Math.max(nowRight, intervals[i][1]);
            } else {
                ans.add(nowRight - nowLeft + 1);
                nowLeft = intervals[i][0];
                nowRight = intervals[i][1];
            }
        }
        ans.add(nowRight - nowLeft + 1);
        return ans;
    }

    // 56. 合并区间
    public int[][] merge(int[][] intervals) {
        // 1 <= intervals.length <= 104
        int len = intervals.length;
        Arrays.sort(intervals, (o1, o2) -> Integer.compare(o1[0], o2[0]));
        List<int[]> list = new ArrayList<>();
        int nowLeft = intervals[0][0], nowRight = intervals[0][1];
        for (int i = 1; i < len; i++) {
            if (nowRight >= intervals[i][0]) {
                nowRight = Math.max(nowRight, intervals[i][1]);
            } else {
                list.add(new int[]{nowLeft, nowRight});
                nowLeft = intervals[i][0];
                nowRight = intervals[i][1];
            }
        }
        list.add(new int[]{nowLeft, nowRight});
        int[][] ans = new int[list.size()][2];
        for (int i = 0; i < list.size(); i++) {
            ans[i] = list.get(i);
        }
        return ans;
    }

    // 738. 单调递增的数字
    public int monotoneIncreasingDigits(int n) {
        List<Integer> list = new ArrayList<>();
        // 332 -> [2, 3, 3]
        while (n > 0) {
            list.add(n % 10);
            n /= 10;
        }
        // [2, 3, 3] -> [9, 9, 2]
        int len_list = list.size();
        int pos_set_9 = -1;
        for (int i = 1; i < len_list; i++) {
            if (list.get(i) > list.get(i - 1)) {
                pos_set_9 = i - 1;
                list.set(i, list.get(i) - 1);
            }
        }
        for (int i = 0; i <= pos_set_9; i++) {
            list.set(i, 9);
        }
        // [9, 9, 2] -> 299
        int ans = 0;
        for (int i = len_list - 1; i >= 0; i--) {
            ans = 10 * ans + list.get(i);
        }
        return ans;
    }

    // 968. 监控二叉树
    public int minCameraCover(TreeNode root) {
        // 树型dp ※※※
        int[] ans = treeDP(root);
        return Math.min(ans[0], ans[1]);
    }

    private int[] treeDP(TreeNode root) {
        // dp[0] 当前节点装相机 dp[1] 当前节点不装相机但被覆盖到了 dp[2] 当前节点不装相机但没覆盖到
        int[] dp = new int[3]; // dp[i]表示情况i下需要的最少相机数量
        if (root == null) {
            dp[0] = 1000; // 实际中可以换为节点数量，等于节点数量时，代表不可能
            return dp;
        }
        int[] left = treeDP(root.left);
        int[] right = treeDP(root.right);
        // 当前节点装了相机，返回左子所有情况的最小情况+右子所有情况的最小情况+1（自己装的）
        dp[0] = Math.min(left[0], Math.min(left[1], left[2])) + Math.min(right[0], Math.min(right[1], right[2])) + 1;
        // 当前节点没装相机，被覆盖，说明左右子至少有一个是装了相机的情况0，返回左子装右子没装和右子装左子没装和都装了这3种情况的最小值
        dp[1] = Math.min(Math.min(left[0] + Math.min(right[0], right[1]), right[0] + Math.min(left[0], left[1])), left[0] + right[0]);
        // 当前节点没装相机，没被覆盖，说明左右都没装，但已经被覆盖
        dp[2] = left[1] + right[1];
        return dp;
    }
}
